package leetcode.problems.P3无重复字符的最长子串;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LengthOfLongestSubstring {
}

// 哈希表 + 滑动窗口
class Solution1 {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len < 2) return len;
        Map<Character, Integer> mp = new HashMap<>();
        mp.put(s.charAt(0), 0);
        int left = 0, right = 1, maxLen = 1;
        while (right < len) {
            char c = s.charAt(right);
            if (mp.containsKey(c)) {
                int leftEnd = mp.get(c) + 1;
                while (left < leftEnd) {
                    mp.remove(s.charAt(left++));
                }
            } else {
                maxLen = Math.max(maxLen, right - left + 1);
            }
            mp.put(c, right);
            right++;
        }
        return maxLen;
    }
}

// 集合 + 滑动窗口
class Solution2 {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len < 2) return len;
        Set<Character> st = new HashSet<>();
        st.add(s.charAt(0));
        int left = 0, right = 1, maxLen = 1;
        while (right < len) {
            char c = s.charAt(right);
            if (st.contains(c)) {
                char leftCh = s.charAt(left);
                while (leftCh != c) {
                    st.remove(leftCh);
                    leftCh = s.charAt(++left);
                }
                ++left;
            } else {
                maxLen = Math.max(maxLen, right - left + 1);
            }
            st.add(c);
            right++;
        }
        return maxLen;
    }
}

// 哈希表 + 滑动窗口 + 省去移动左指针
class Solution3 {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> mp = new HashMap<>();
        int maxLen = 0, left = 0, right = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            if (mp.containsKey(c)) {
                maxLen = Math.max(maxLen, right - left);
                left = Math.max(left, mp.get(c) + 1);
            }
            mp.put(c, right);
            right++;
        }
        return Math.max(maxLen, right - left);
    }
}